extern crate rand;
use rand::prelude::*;
use std::mem::size_of;
use std::num::Wrapping;

/*
type DBlock = u128;

type Block = u64;

type Byte = u8;

type Int = i32;
*/

pub const MUL_BLOCK_THRESHOLD: usize = 400;
pub const MUL_THRESHOLD: usize = 1200;
pub const DIV_THRESHOLD: usize = 80;
pub const DIV_OFFSET: usize = 40;

pub const DBLOCK_BIT: usize = size_of::<u128>() * 8;
pub const BLOCK_BIT: usize = size_of::<u64>() * 8;
pub const BYTE_BIT: usize = size_of::<u8>() * 8;
pub const BLOCK_SIZE: usize = size_of::<u64>();
pub const BLOCK_MAX: u64 = u64::MAX;
pub const INT_MAX: i32 = i32::MAX;

pub const BLOCK_BIAS: u128 = (u64::MAX as u128) + 1;

/* multiplicative inverse mod 2^k
 * http://marc-b-reynolds.github.io/math/2017/09/18/ModInverse.html
 */
#[inline]
pub fn mod_inverse64(a: u64) -> u64 {
    let a = Wrapping(a);
    let mut x: Wrapping<u64>;
    x = (a * a) + a - Wrapping(1u64); // 4 bits
    x *= Wrapping(2u64) - a * x; // 8 bits
    x *= Wrapping(2u64) - a * x; // 16 bits
    x *= Wrapping(2u64) - a * x; // 32 bits
    x *= Wrapping(2u64) - a * x; // 64 bits
    x.0
}

/* untested */
#[inline]
pub fn mod_inverse128(a: u128) -> u128 {
    let a = Wrapping(a);
    let mut x: Wrapping<u128>;
    x = (a * a) + a - Wrapping(1u128); // 4 bits
    x *= Wrapping(2u128) - a * x; // 8 bits
    x *= Wrapping(2u128) - a * x; // 16 bits
    x *= Wrapping(2u128) - a * x; // 32 bits
    x *= Wrapping(2u128) - a * x; // 64 bits
    x *= Wrapping(2u128) - a * x; // 128 bits
    x.0
}

pub const BNEXPMOD_MAX_WINDOW: i32 = 7;
pub const BNEXPMOD_THRESHOLD: [i32; 7] = [5, 23, 80, 240, 672, 1792, INT_MAX];

/* get random dword number with b bits, b <= BlockBit */
#[inline]
pub fn random_u64(rng: &mut StdRng, b: u32) -> u64 {
    assert!(b > 0 && b <= (BLOCK_BIT as u32));
    let mut x: u64 = rng.next_u64();
    match b {
        64 => x,
        _ => x & ((1u64 << b) - 1),
    }
}

pub const DEFAULT_PRECISION: i32 = 100;

/* Sorenson and Webster
 * n < 3317044064679887385961981, it is enough to test
 * a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.
 */
pub const PRIME_PROBE_THRESHOLD: u32 = 95;

pub const PRIME_PRODUCT: u64 = 152125131763605; //3*5*7*11*13*17*19*23*29*31*37*41

pub const SMALL_PRIMES: [u64; 12] = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41];

#[inline]
pub fn fill(a: &mut [u64], b: u64) {
    for ai in a.iter_mut() {
        *ai = b
    }
}

#[inline]
pub fn diff(a: usize, b: usize) -> usize {
    if a > b {
        a - b
    } else {
        b - a
    }
}

#[macro_use]
#[allow(unused)]
mod comparator {
    macro_rules! min {
        ($x:expr, $y:expr) => {
            if $x < $y {
                $x
            } else {
                $y
            }
        };
    }

    macro_rules! max {
        ($x:expr, $y:expr) => {
            if $x < $y {
                $y
            } else {
                $x
            }
        };
    }
}
